package com.wk.arth.od;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 表达式求值
 * 中缀表达式 人识别 不仅依靠运算符的优先级，也要处理括号的优先级 a+b-c*d
 * 后缀表达式（逆波兰表达式） 机器识别 没有括号，只有操作数和运算符，且运算符放在操作数的后面 ab+cd*-
 * 前缀表达式（波兰表达式） 也是一种没有括号的算术表达式，其运算符写在前面，操作数写在后面 -+ab*cd
 * 1.栈解法 运算符栈 中缀转后缀表达式  然后入栈计算
 * 2.中缀表达式转二叉树（中序），然后后序遍历即得到后缀表达式，然后计算
 * 1+(2-3)*6-9 => 123-6*+9-
 * a+(b-c*d)/e
 * 9+(3-1)×3+8÷2 => 931-3*+82/+
 * @author wukai
 * @date 2023/4/18 12:59
 */
public class Biao_da_shi {
    public static void main(String[] args) {
        System.out.println(getMidExpressList("20+33*(44-34)"));
        System.out.println(midToLast("20+33*(44-34+2+3*3)"));
        System.out.println(cal("20+33*(44-34+2+3*3)"));
    }

    private static int cal(String s) {
        List<String> list = midToLast(s);
        Stack<Integer> stack = new Stack<>();
        for (String item : list) {
            if(item.matches("\\d+")){
                stack.push(Integer.parseInt(item));
            }else{
                int a1 = stack.pop();
                int a2 = stack.pop();
                int res=0;
                if(item.equals("+")){
                    res = a2+a1;
                }else if(item.equals("-")){
                    res = a2-a1;
                }else if(item.equals("*")){
                    res = a2*a1;
                }else if(item.equals("/")){
                    if(a1 == 0){
                        throw new RuntimeException("表达式有问题");
                    }
                    res = a2/a1;
                }
                stack.push(res);
            }
        }
        return stack.pop();
    }

    /**
     * 中缀表达式转后缀表达式
     * @param s
     * @return
     */
    public static List<String> midToLast(String s){
        // 运算符栈
        Stack<String> stack = new Stack<>();
        // 输出结果 后缀表达式
        List<String> res = new ArrayList<>();
        List<String> strList = getMidExpressList(s);
        for (String s1 : strList) {
            if(s1.matches("\\d+")){
                res.add(s1);
            }else if(s1.equals("(")){
                stack.push(s1);
            }else if(s1.equals(")")){
                String cur;
                while (!( cur = stack.pop()).equals("(")){
                    res.add(cur);
                }
            }else{
                while (stack.size() >0 && Operation.getValue(s1)<=Operation.getValue(stack.peek())){
                    res.add(stack.pop());
                }
                stack.push(s1);
            }
        }
        while (stack.size()>0){
            res.add(stack.pop());
        }
        return res;
    }

    /**
     * 中缀表达式转成数组
     * @param s
     * @return
     */
    private static List<String> getMidExpressList(String s) {
        List<String> list = new ArrayList<>();
        int i = 0;
        char c;
        do{
            c=s.charAt(i);
            // 48 =>'0' 57=>'9'
            if(c<48 || c>57){
                //不是数字
                list.add(""+c);
                i++;
            }else{
                // 2位数字
                String num = ""+c;
                i++;
                while (i<s.length()&&s.charAt(i)>=48 && s.charAt(i)<=57){
                    num = num+s.charAt(i);
                    i++;
                }
                list.add(num);
            }
        }while (i<s.length());
        return list;
    }
}
class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation){
        switch (operation){
            case "+":
                return ADD;
            case "-":
                return SUB;
            case "*":
                return MUL;
            case "/":
                return DIV;
            default:
                // System.out.println("不存在该运算符");
                // ( 优先级0
                return 0;
        }
    }

}
